package top.humbleyuan.tree;

import top.humbleyuan.datastructure.tree.TreeNode;

/**
 * @Author HumbleYuan
 * @Date 2020/5/19 19:32
 * @Des 判断是否是平衡二叉树
 */
public class LeetCode_110 {
    public static void main(String[] args) {
        TreeNode head = new TreeNode(2);
        head.formTree();

        System.out.println(getHeight(head) != -1);
    }


    public static int getHeight(TreeNode treeNode) {
        if(treeNode == null) {
            return 0;
        }

        // 计算左子树
        int lDepth = getHeight(treeNode.left);
        // 左子树就不平衡则提前中断
        if(lDepth == -1) {
            return lDepth;
        }

        // 计算右子树
        int rDepth = getHeight(treeNode.right);
        // 右子树就不平衡则提前中断
        if(rDepth == -1) {
            return rDepth;
        }

        // max是因为比较高度差，比较的是左右子树最大高度的差
        return Math.abs(lDepth - rDepth) > 1 ? -1 : Math.max(lDepth, rDepth) + 1;
    }
}
